//
// Created by 86138 on 2025/6/8.
//
#include "DuLinkList.h"
#include <iostream>
using namespace std;

namespace sweetcookie2 {
    void InitList(DuLinkList &L) {
        L = (DuLinkList) malloc(sizeof(DuLNode));
        if (!L) exit(OVERFLOW);
        L->prior = L->next = L;
    }

    void ClearList(DuLinkList L) {
        DuLNode *p, *q;
        p = L->next;
        while (p != L) {
            q = p->next;
            free(p);
            p = q;
        }
        L->prior = L->next = L;

            // 下面这块更简洁，连指针q也省了
//        DuLNode *p = L->next;
//        while (p != L) {
//            p = p->next;
//            free(p->prior);
//        }
//        L->prior = L->next = L;
    }

    void DestroyList(DuLinkList &L) {
        ClearList(L);
        free(L);
        L = nullptr;
    }

    Status ListEmpty(DuLinkList L) {
        if (L->next == L) return true;
        return false;
    }

    int ListLength(DuLinkList L) {
        int length = 0;
        DuLNode *p = L->next;
        while (p != L) {
            length++;
            p = p->next;
        }
        return length;
    }

    Status GetElem(DuLinkList L, int i, ElemType &e) {
        DuLNode *p = L->next;
        int j = 1;
        while (p != L && j < i) {
            j++;
            p = p->next;
        }
        if (p == L || j > i) {
            cout << "获取元素位置i不合法" << endl;
            return ERROR;
        }
        e = p->data;
        return OK;
    }

    int LocateElem(DuLinkList L, ElemType e, Status(*compare) (ElemType, ElemType)) {
        DuLNode *p = L->next;
        int j = 0;
        while (p != L) {
            j++;
            if (compare(p->data, e)) {
                return j;
            }
            p = p->next;
        }
        return 0;
    }

    DuLNode* GetElemP(DuLinkList L, int i) {
        if (i <= 0 || i > ListLength(L) + 1) {
            cout << "获取元素i的位置不合法" << endl;
            return nullptr;
        }
        DuLNode *p = L;
        int j = 0;
        while (j < i) {
            j++;
            p = p->next;
        }
        return p;
    }

    Status PriorElem(DuLinkList L, ElemType cur_e, ElemType &pre_e) {
        // 若cur_e是L的数据元素且不是第一个，则用pre_e返回它的前驱，返回OK；否则操作失败，pre_e无定义，返回ERROR
        // 我的问题是这样最后一个数据元素无法被作为pre_e被找到了
        DuLNode *p;
        p = L->next->next; // 指向第二个节点，指向第一个无意义
        while (p != L && p->data != cur_e) {
            p = p->next;
        }
        if (p == L) {
            cout << "没有找到" << endl;
            return ERROR;
        }
        pre_e = p->prior->data;
        return OK;
    }

    Status NextElem(DuLinkList L, ElemType cur_e, ElemType &next_e) {
        // 若cur_e是L的数据元素且不是最后一个，则用next_e返回它的后继，返回OK；否则操作失败，pre_e无定义，返回ERROR
        DuLNode *p;
        p = L;
        while (p->next != L && p->data != cur_e) {
            p = p->next;
        }
        if (p->next == L) {
            cout << "没有找到" << endl;
            return ERROR;
        }
        next_e = p->next->data;
        return OK;
    }

    void ListTraverse(DuLinkList L) {
        DuLNode *p = L->next;
        while (p != L) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    }

    void ListTraverseBack(DuLinkList L) {
        DuLNode *p = L->prior;
        while (p != L) {
            cout << p->data << " ";
            p = p->prior;
        }
        cout << endl;
    }

    Status ListInsert(DuLinkList L, int i, ElemType e) {
        DuLNode *p = GetElemP(L, i);
        if (p == nullptr) {
            cout << "插入位置i不合法" << endl;
            return ERROR;
        }
        DuLNode *s = (DuLNode *) malloc(sizeof(DuLNode));
        s->data = e;
        s->prior = p->prior;
        p->prior->next = s;
        s->next = p;
        p->prior = s;

        return OK;
    }

    Status ListDelete(DuLinkList L, int i, ElemType &e) {
        DuLNode *p = GetElemP(L, i);
        if (p == nullptr) {
            cout << "删除位置i不合法" << endl;
            return ERROR;
        }
        e = p->data;
        p->prior->next = p->next;
        p->next->prior = p->prior;
        free(p);

        return OK;
    }
}

//using namespace sweetcookie2;
//int main() {
//    system("chcp 65001");
//    DuLinkList L;
//    InitList(L);
//    int i, n = 4;
//    Status j;
//    ElemType e;
//    for (i = 1; i <= 5; i++) {
//        ListInsert(L, i, i);
//    }
//    cout << "逆序输出链表：";
//    ListTraverseBack(L);
//    j = GetElem(L, 2, e);
//    if (j)
//        cout << "链表的第2个元素值为" << e << endl;
//    else
//        cout << "不存在第2个元素" << endl;
//    i = LocateElem(L, n, equal);
//    if (i)
//        cout << "等于" << n << "的元素是第" << i << "个" << endl;
//    else
//        cout << "没有等于" << n << "的元素" << endl;
//    j = PriorElem(L, n, e);
//    if (j)
//        cout << n << "的前驱是" << e << endl;
//    else
//        cout << "不存在" << n << "的前驱" << endl;
//    j = NextElem(L, n, e);
//    if (j)
//        cout << n << "的后继是" << e << endl;
//    else
//        cout << "不存在" << n << "的后继" << endl;
//
//    ListDelete(L, 2, e);
//    cout << "删除第2个节点，值为" << e << "，其余节点为：";
//    ListTraverse(L);
//    cout << "链表的元素个数是" << ListLength(L) << endl;
//    cout << "链表是否为空？" << ListEmpty(L) << endl;
//    ClearList(L);
//    cout << "清空后，链表是否为空？" << ListEmpty(L) << endl;
//    DestroyList(L);
//
//    return 0;
//}